package java.util;


public abstract class AbstractCollection<E> implements Collection<E>,
		Iterable<E> {
	/**
	 * The main constructor, for use by subclasses.
	 */
	protected AbstractCollection() {
	}

	/**
	 * Return an Iterator over this collection. The iterator must provide the
	 * hasNext and next methods and should in addition provide remove if the
	 * collection is modifiable.
	 * 
	 * @return an iterator
	 */
	public abstract Iterator<E> iterator();

	/**
	 * Return the number of elements in this collection. If there are more than
	 * Integer.MAX_VALUE elements, return Integer.MAX_VALUE.
	 * 
	 * @return the size
	 */
	public abstract int size();

	/**
	 * Add an object to the collection (optional operation). This implementation
	 * always throws an UnsupportedOperationException - it should be overridden
	 * if the collection is to be modifiable. If the collection does not accept
	 * duplicates, simply return false. Collections may specify limitations on
	 * what may be added.
	 * 
	 * @param o
	 *            the object to add
	 * @return true if the add operation caused the Collection to change
	 * @throws UnsupportedOperationException
	 *             if the add operation is not supported on this collection
	 * @throws NullPointerException
	 *             if the collection does not support null
	 * @throws ClassCastException
	 *             if the object is of the wrong type
	 * @throws IllegalArgumentException
	 *             if some aspect of the object prevents it from being added
	 */
	public boolean add(E o) {
		throw new UnsupportedOperationException();
	}

	/**
	 * Add all the elements of a given collection to this collection (optional
	 * operation). This implementation obtains an Iterator over the given
	 * collection and iterates over it, adding each element with the add(Object)
	 * method (thus this method will fail with an UnsupportedOperationException
	 * if the add method does). The behavior is unspecified if the specified
	 * collection is modified during the iteration, including the special case
	 * of trying addAll(this) on a non-empty collection.
	 * 
	 * @param c
	 *            the collection to add the elements of to this collection
	 * @return true if the add operation caused the Collection to change
	 * @throws UnsupportedOperationException
	 *             if the add operation is not supported on this collection
	 * @throws NullPointerException
	 *             if the specified collection is null
	 * @throws ClassCastException
	 *             if the type of any element in c is not a valid type for
	 *             addition.
	 * @throws IllegalArgumentException
	 *             if some aspect of any element in c prevents it being added.
	 * @throws NullPointerException
	 *             if any element in c is null and this collection doesn't allow
	 *             null values.
	 * @see #add(Object)
	 */
	public boolean addAll(Collection<? extends E> c) {
		Iterator<? extends E> itr = c.iterator();
		boolean modified = false;
		int pos = c.size();
		while (--pos >= 0)
			modified |= add(itr.next());
		return modified;
	}

	/**
	 * Remove all elements from the collection (optional operation). This
	 * implementation obtains an iterator over the collection and calls next and
	 * remove on it repeatedly (thus this method will fail with an
	 * UnsupportedOperationException if the Iterator's remove method does) until
	 * there are no more elements to remove. Many implementations will have a
	 * faster way of doing this.
	 * 
	 * @throws UnsupportedOperationException
	 *             if the Iterator returned by iterator does not provide an
	 *             implementation of remove
	 * @see Iterator#remove()
	 */
	public void clear() {
		Iterator<E> itr = iterator();
		int pos = size();
		while (--pos >= 0) {
			itr.next();
			itr.remove();
		}
	}

	/**
	 * Test whether this collection contains a given object. That is, if the
	 * collection has an element e such that (o == null ? e == null :
	 * o.equals(e)). This implementation obtains an iterator over the collection
	 * and iterates over it, testing each element for equality with the given
	 * object. If it is equal, true is returned. Otherwise false is returned
	 * when the end of the collection is reached.
	 * 
	 * @param o
	 *            the object to remove from this collection
	 * @return true if this collection contains an object equal to o
	 */
	public boolean contains(Object o) {
		Iterator<E> itr = iterator();
		int pos = size();
		while (--pos >= 0)
			if (equals(o, itr.next()))
				return true;
		return false;
	}

	/**
	 * Tests whether this collection contains all the elements in a given
	 * collection. This implementation iterates over the given collection,
	 * testing whether each element is contained in this collection. If any one
	 * is not, false is returned. Otherwise true is returned.
	 * 
	 * @param c
	 *            the collection to test against
	 * @return true if this collection contains all the elements in the given
	 *         collection
	 * @throws NullPointerException
	 *             if the given collection is null
	 * @see #contains(Object)
	 */
	public boolean containsAll(Collection<?> c) {
		Iterator<?> itr = c.iterator();
		int pos = c.size();
		while (--pos >= 0)
			if (!contains(itr.next()))
				return false;
		return true;
	}

	/**
	 * Test whether this collection is empty. This implementation returns size()
	 * == 0.
	 * 
	 * @return true if this collection is empty.
	 * @see #size()
	 */
	public boolean isEmpty() {
		return size() == 0;
	}

	/**
	 * Remove a single instance of an object from this collection (optional
	 * operation). That is, remove one element e such that
	 * <code>(o == null ? e == null : o.equals(e))</code>, if such an element
	 * exists. This implementation obtains an iterator over the collection and
	 * iterates over it, testing each element for equality with the given
	 * object. If it is equal, it is removed by the iterator's remove method
	 * (thus this method will fail with an UnsupportedOperationException if the
	 * Iterator's remove method does). After the first element has been removed,
	 * true is returned; if the end of the collection is reached, false is
	 * returned.
	 * 
	 * @param o
	 *            the object to remove from this collection
	 * @return true if the remove operation caused the Collection to change, or
	 *         equivalently if the collection did contain o.
	 * @throws UnsupportedOperationException
	 *             if this collection's Iterator does not support the remove
	 *             method
	 * @see Iterator#remove()
	 */
	public boolean remove(Object o) {
		Iterator<E> itr = iterator();
		int pos = size();
		while (--pos >= 0)
			if (equals(o, itr.next())) {
				itr.remove();
				return true;
			}
		return false;
	}

	/**
	 * Remove from this collection all its elements that are contained in a
	 * given collection (optional operation). This implementation iterates over
	 * this collection, and for each element tests if it is contained in the
	 * given collection. If so, it is removed by the Iterator's remove method
	 * (thus this method will fail with an UnsupportedOperationException if the
	 * Iterator's remove method does).
	 * 
	 * @param c
	 *            the collection to remove the elements of
	 * @return true if the remove operation caused the Collection to change
	 * @throws UnsupportedOperationException
	 *             if this collection's Iterator does not support the remove
	 *             method
	 * @throws NullPointerException
	 *             if the collection, c, is null.
	 * @see Iterator#remove()
	 */
	public boolean removeAll(Collection<?> c) {
		return removeAllInternal(c);
	}

	/**
	 * Remove from this collection all its elements that are contained in a
	 * given collection (optional operation). This implementation iterates over
	 * this collection, and for each element tests if it is contained in the
	 * given collection. If so, it is removed by the Iterator's remove method
	 * (thus this method will fail with an UnsupportedOperationException if the
	 * Iterator's remove method does). This method is necessary for ArrayList,
	 * which cannot publicly override removeAll but can optimize this call.
	 * 
	 * @param c
	 *            the collection to remove the elements of
	 * @return true if the remove operation caused the Collection to change
	 * @throws UnsupportedOperationException
	 *             if this collection's Iterator does not support the remove
	 *             method
	 * @throws NullPointerException
	 *             if the collection, c, is null.
	 * @see Iterator#remove()
	 */
	// Package visible for use throughout java.util.
	boolean removeAllInternal(Collection<?> c) {
		Iterator<E> itr = iterator();
		boolean modified = false;
		int pos = size();
		while (--pos >= 0)
			if (c.contains(itr.next())) {
				itr.remove();
				modified = true;
			}
		return modified;
	}

	/**
	 * Remove from this collection all its elements that are not contained in a
	 * given collection (optional operation). This implementation iterates over
	 * this collection, and for each element tests if it is contained in the
	 * given collection. If not, it is removed by the Iterator's remove method
	 * (thus this method will fail with an UnsupportedOperationException if the
	 * Iterator's remove method does).
	 * 
	 * @param c
	 *            the collection to retain the elements of
	 * @return true if the remove operation caused the Collection to change
	 * @throws UnsupportedOperationException
	 *             if this collection's Iterator does not support the remove
	 *             method
	 * @throws NullPointerException
	 *             if the collection, c, is null.
	 * @see Iterator#remove()
	 */
	public boolean retainAll(Collection<?> c) {
		return retainAllInternal(c);
	}

	/**
	 * Remove from this collection all its elements that are not contained in a
	 * given collection (optional operation). This implementation iterates over
	 * this collection, and for each element tests if it is contained in the
	 * given collection. If not, it is removed by the Iterator's remove method
	 * (thus this method will fail with an UnsupportedOperationException if the
	 * Iterator's remove method does). This method is necessary for ArrayList,
	 * which cannot publicly override retainAll but can optimize this call.
	 * 
	 * @param c
	 *            the collection to retain the elements of
	 * @return true if the remove operation caused the Collection to change
	 * @throws UnsupportedOperationException
	 *             if this collection's Iterator does not support the remove
	 *             method
	 * @throws NullPointerException
	 *             if the collection, c, is null.
	 * @see Iterator#remove()
	 */
	// Package visible for use throughout java.util.
	boolean retainAllInternal(Collection<?> c) {
		Iterator<E> itr = iterator();
		boolean modified = false;
		int pos = size();
		while (--pos >= 0)
			if (!c.contains(itr.next())) {
				itr.remove();
				modified = true;
			}
		return modified;
	}

	/**
	 * Return an array containing the elements of this collection. This
	 * implementation creates an Object array of size size() and then iterates
	 * over the collection, setting each element of the array from the value
	 * returned by the iterator. The returned array is safe, and is not backed
	 * by the collection.
	 * 
	 * @return an array containing the elements of this collection
	 */
	public Object[] toArray() {
		Iterator<E> itr = iterator();
		int size = size();
		Object[] a = new Object[size];
		for (int pos = 0; pos < size; pos++)
			a[pos] = itr.next();
		return a;
	}

	/**
	 * Copy the collection into a given array if it will fit, or into a
	 * dynamically created array of the same run-time type as the given array if
	 * not. If there is space remaining in the array, the first element after
	 * the end of the collection is set to null (this is only useful if the
	 * collection is known to contain no null elements, however). This
	 * implementation first tests whether the given array is large enough to
	 * hold all the elements of the collection. If not, the reflection API is
	 * used to allocate a new array of the same run-time type. Next an iterator
	 * is obtained over the collection and the elements are placed in the array
	 * as they are returned by the iterator. Finally the first spare element, if
	 * any, of the array is set to null, and the created array is returned. The
	 * returned array is safe; it is not backed by the collection. Note that
	 * null may not mark the last element, if the collection allows null
	 * elements.
	 * 
	 * @param a
	 *            the array to copy into, or of the correct run-time type
	 * @return the array that was produced
	 * @throws NullPointerException
	 *             if the given array is null
	 * @throws ArrayStoreException
	 *             if the type of the array precludes holding one of the
	 *             elements of the Collection
	 */
	public <T> T[] toArray(T[] a) {
		int size = size();
		if (a.length > size) {
			a[size] = null;
		}
		Iterator<E> itr = iterator();
		for (int pos = 0; pos < size; pos++)
			a[pos] = (T) (itr.next());
		return a;
	}

	/**
	 * Creates a String representation of the Collection. The string returned is
	 * of the form "[a, b, ...]" where a and b etc are the results of calling
	 * toString on the elements of the collection. This implementation obtains
	 * an Iterator over the Collection and adds each element to a StringBuffer
	 * as it is returned by the iterator. "<this>" is inserted when the
	 * collection contains itself (only works for direct containment, not for
	 * collections inside collections).
	 * 
	 * @return a String representation of the Collection
	 */
	public String toString() {
		Iterator<E> itr = iterator();
		StringBuilder r = new StringBuilder("[");
		boolean hasNext = itr.hasNext();
		while (hasNext) {
			Object o = itr.next();
			if (o == this)
				r.append("<this>");
			else
				r.append(o);
			hasNext = itr.hasNext();
			if (hasNext)
				r.append(", ");
		}
		r.append("]");
		return r.toString();
	}

	/**
	 * Compare two objects according to Collection semantics.
	 * 
	 * @param o1
	 *            the first object
	 * @param o2
	 *            the second object
	 * @return o1 == null ? o2 == null : o1.equals(o2)
	 */
	static final boolean equals(Object o1, Object o2) {
		return o1 == null ? o2 == null : o1.equals(o2);
	}

	/**
	 * Hash an object according to Collection semantics.
	 * 
	 * @param o
	 *            the object to hash
	 * @return o1 == null ? 0 : o1.hashCode()
	 */
	static final int hashCode(Object o) {
		return o == null ? 0 : o.hashCode();
	}
}
